package subString;

import java.util.HashMap;

/**
 * @className: LeetCode_76
 * @Description: 最小覆盖字串
 * @author: kunkun
 * @date: 2025/3/3 21:11
 */
public class LeetCode_76 {

    public String minWindow(String s, String t) {
//        return (solution_1(s,t,0,s.length()-1)==null)?"":solution_1(s,t,0,s.length()-1);
//        return solution_2(s,t);
        return solution_3(s,t);
    }

    public static void main(String[] args) {
        LeetCode_76 ob = new LeetCode_76();
        System.out.println(ob.minWindow("ADOBECODEBANC", "ABC"));//BANC
        System.out.println(ob.minWindow("a", "a"));//a
        System.out.println(ob.minWindow("a", "aa"));//""
        System.out.println(ob.minWindow("ab", "a"));//a
        System.out.println(ob.minWindow("AABC", "AC"));//ABC
        System.out.println(ob.minWindow("aaaaaaaaaaaabbbbbcdd", "abcdd"));//abbbbbcdd
    }

    /**
     * @Author kunkun
     * @Description 方法1：暴力递归，时间复杂度：O（m*2^n）
     * @Date 22:43 2025/3/3
     * @Param
     * @return
     **/
    public String solution_1(String s, String t,int start,int end){
        //1. 情况判断
        if (end-start+1<t.length()){
            return null;
        }
        //2. 判断是否存在t
        if (check(s,t,start,end)){
            //2.1 存在分析属于哪个片段
            String result1 = solution_1(s,t,start,end-1);
            String result2 = solution_1(s,t,start+1,end);
            if (result1!=null && result2==null){
                return result1;
            } else if (result1==null && result2!=null) {
                return result2;
            }else if (result1!=null && result2!=null){
                return (result1.length()<result2.length())?result1:result2;
            }else {
                return s.substring(start,end+1);
            }
        }else {
            return null;
        }


    }

    /**
     * @Author kunkun
     * @Description 方法2：动态规划，时间复杂度：O（n^3）,超时
     * @Date 22:43 2025/3/3
     * @Param
     * @return
     **/
    public String solution_2(String s, String t){
        //1. 定义二维数组，默认值填充
        String[][] results = new String[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if(j-i<t.length()-1){
                    results[i][j]=null;
                } else if (j-i == t.length()-1) {
                    if (check(s,t,i,j)){
                        results[i][j]=s.substring(i,j+1);
                    }else{
                        results[i][j]=null;
                    }
                }
            }
        }
        //2. 逐行计算
        for (int line = 0; line < s.length()-1; line++) {
            for (int i=0,j = line+t.length(); j < s.length(); i++,j++) {
                if (check(s,t,i,j)){
                    String result1 = results[i][j-1];
                    String result2 = results[i+1][j];

                    if (result1!=null && result2==null){
                        results[i][j]= result1;
                    } else if (result1==null && result2!=null) {
                        results[i][j]= result2;
                    }else if (result1!=null && result2!=null){
                        results[i][j]= (result1.length()<result2.length())?result1:result2;
                    }else {
                        results[i][j]= s.substring(i,j+1);
                    }
                }else {
                    results[i][j]=null;
                }
            }
        }
        return (results[0][s.length()-1]==null)?"":results[0][s.length()-1];



    }

    /**
     * @Author kunkun
     * @Description 方法3：变长滑动窗口，时间复杂度：O（n*m）
     * @Date 22:43 2025/3/3
     * @Param
     * @return
     **/
    public String solution_3(String s, String t){
        //0. 特殊情况排除
        if (t.length()>s.length()){
            return "";
        }
        //1. 定义窗口的左右指针,两个map(map1：窗口中各字符个数，map2：t中各字符数目)
        int left =0,right =t.length()-1;
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();
        for (int i = 0; i < right; i++) {
            map1.put(s.charAt(i), map1.getOrDefault(s.charAt(i),0)+1);
        }
        for (int i = 0; i < t.length(); i++) {
            map2.put(t.charAt(i), map2.getOrDefault(t.charAt(i),0)+1);
        }

        //2. 循环遍历
        String minStr = null;
        for (; right < s.length(); right++) {
            //2.1 新加入元素入map1
            map1.put(s.charAt(right), map1.getOrDefault(s.charAt(right),0)+1);

            //2.2 判断是否包含map2
            if (checkByMap(map1,map2)){     //包含
                //2.2.1 移动左指针看是否能缩小
                while (checkByMap(map1,map2)){
                    if (map1.get(s.charAt(left))==1){
                        map1.remove(s.charAt(left));
                    }else {
                        map1.put(s.charAt(left),map1.get(s.charAt(left))-1);
                    }
                    left++;
                }
                left--;
                map1.put(s.charAt(left), map1.getOrDefault(s.charAt(left),0)+1);

                //2.2.2 记录结果
                if (minStr==null){
                    minStr = s.substring(left,right+1);
                }else {
                    minStr = (right-left+1<minStr.length())?s.substring(left,right+1):minStr;
                }

            }
        }

        return (minStr==null)?"":minStr;
    }

    //检查字段中是否存在t
    private boolean checkByMap(HashMap<Character, Integer> map1, HashMap<Character, Integer> map2) {

        for (Character c : map2.keySet()) {
            Integer count1  = map1.getOrDefault(c,0);
            Integer count2 = map2.get(c);
            if (count1<count2){
                return false;
            }
        }
        return true;


    }


    //检查字段中是否存在t
    public Boolean check(String s,String t,int start,int end){
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = start; i < end+1; i++) {
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }
        //检查
        for (int i = 0; i < t.length(); i++) {
            if (map.containsKey(t.charAt(i))){
                Integer integer = map.get(t.charAt(i));
                if (integer==1){
                    map.remove(t.charAt(i));
                }else {
                    map.put(t.charAt(i),integer-1);
                }
            }else{
                return false;
            }
        }
        return true;

    }


}
